#include <vector>
using namespace std;

class NumMatrix {
  vector<vector<int>> numSum;

public:
  NumMatrix(vector<vector<int>> &matrix) {
    int height = matrix.size(), width = matrix[0].size();
    numSum.resize(height);
    for (auto &item : numSum) {
      item.resize(width);
    }

    numSum[0][0] = matrix[0][0];
    for (int j = 1; j < width; ++j) {
      numSum[0][j] = numSum[0][j - 1] + matrix[0][j];
    }

    for (int i = 1; i < height; ++i) {
      numSum[i][0] = numSum[i - 1][0] + matrix[i][0];
      for (int j = 1; j < width; ++j) {
        numSum[i][j] = numSum[i - 1][j] + numSum[i][j - 1] -
                       numSum[i - 1][j - 1] + matrix[i][j];
      }
    }
  }

  int sumRegion(int row1, int col1, int row2, int col2) {
    if (row1 == 0) {
      if (col1 == 0) {
        return numSum[row2][col2];
      } else {
        return numSum[row2][col2] - numSum[row2][col1 - 1];
      }
    } else {
      if (col1 == 0) {
        return numSum[row2][col2] - numSum[row1 - 1][col2];
      } else {
        return numSum[row2][col2] + numSum[row1 - 1][col1 - 1] -
               numSum[row2][col1 - 1] - numSum[row1 - 1][col2];
      }
    }
  }
};
